<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>
    <script>
        var input = [4, 5, 12, 6, 2, 7, 3, 8]
        console.log(GetLeastNumbers_Solution(input, 4))

        function GetLeastNumbers_Solution(input, k) {
            // write code here
            quickSort(input, 0, input.length - 1)
            console.log(input)
            if (k > input.length) {
                return []
            }
            var res = []
            for (let i = 0; i < k; i++) {
                res.push(input[i])
            }
            return res
        }

        function quickSort(input, left, right) {
            if (left >= right) { //如果左边大于等于右边，说明两侧走到交叉点
                return
            }
            var num = input[left] //找出一个基准值进行比较
            var i = left,
                j = right
            while (i != j) {
                while (i < j && input[j] >= num) {
                    j--
                }
                //如果i<j并且找到大于基准值的数字
                while (i < j && input[i] <= num) {
                    i++
                }
                if (i < j) { //i所在的位置是比基准值大的，j所在位置是比基准值小的
                    let temp = input[i]
                    input[i] = input[j]
                    input[j] = temp
                }
            }
            //当i==j时说明i左边都是比基准值小的，而j右边都是比基准值大的 
            input[left] = input[i]
            input[i] = num
                //对剩余的数字进行递归，依次从数字中找到基准值并进行比较、交换
            quickSort(input, left, i - 1)
            quickSort(input, i + 1, right)
        }
    </script>
</body>

</html>